\documentclass[compressed,narroweqnarray,inline]{ieee}
%\documentclass[%
%	%draft,
%	%submission,
%	%compressed,
%	final,
%	%
%	%technote,
%	%internal,
%	%submitted,
%	%inpress,
%	reprint,
%	%
%	%titlepage,
%	notitlepage,
%	%anonymous,
%	narroweqnarray,
%	inline
%	%twoside
%	]{ieee}

\usepackage{ieeefig}
\usepackage{listings}
\usepackage{pdfcolmk}
\usepackage{hyperref}
\usepackage{graphicx}
\usepackage{float}
\usepackage{subfig}
\usepackage{verbatim}
\usepackage{wrapfig}
\usepackage{moreverb}
\usepackage{fancyhdr}
\usepackage{xcolor}
\usepackage{color}
\usepackage{url}

\usepackage{multicol}
\linespread{1.3} % 1.5 line spacing
\begin{document}

%----------------------------------------------------------------------
% Title Information, Abstract and Keywords
%----------------------------------------------------------------------
\title[Data Types in Common Lisp]{%
       An Overview of Data Types and Structures in the Common Lisp Programming Language}

% format author this way for journal articles.
\author[SHORT NAMES]{%
      Anthony Naddeo\member{Student Member}
      \authorinfo{%
      A. Computer Science Undergraduate Student,
      University of Maine, Orono ME 04469, USA,
      Phone: \mbox{(347) 210-0185}, email: \mbox{anthony.naddeo@gmail.com}}
  }

% format author this way for conference proceedings
\author[SHORT NAMES]{%
      Anthony Naddeo\member{Fellow}
      \authorinfo{%
      Computer Science Undergraduate Student\\
      University of Maine, Orono ME 04469, USA\\
      Phone: (347) 210-0185, email: anthony.naddeo@gmail.com}
  }

% specifiy the journal name
\journal{COS 301, 2011}

% Or, specify the conference place and date.
%\confplacedate{Ottawa, Canada, May 19--21, 1997}

% make the title
\maketitle   
\thispagestyle{empty}     
\newpage

\begin{abstract}  
This paper examines the Common Lisp programming language from the point of view of data types and objects, as well as how to interact with and assign values to them. There are also sufficient examples to demonstrate the semantics of various types of expressions -- assignment or otherwise. 
\end{abstract}

% do the keywords
\begin{keywords}
Lisp, programming language, types, Common Lisp, CLOS, object, data
\end{keywords}

%config the listings settings
\lstset{language=Lisp,
identifierstyle=\ttfamily,
breaklines=true,
tabsize=2,
%title=\lstname,
basicstyle=\footnotesize,
keywordstyle=\color[rgb]{0.5,0.5,0},
commentstyle=\color{red},
stringstyle=\color[rgb]{0,0.5,0}}

\pagenumbering{roman}
\newpage

\tableofcontents
\newpage
\pagenumbering{arabic}
 
\begin{multicols}{2}
%----------------------------------------------------------------------
% SECTION I: Introduction
%----------------------------------------------------------------------
\section{Introduction}\label{sec:intro}
\PARstart  The Common Lisp programming language has over a dozen data types explicitly defined in the language specification, some of which include arrays, hash tables, symbols, and characters. In Common Lisp's effort to become as cross platform as possible it has included enough in its core specification to reduce the chance that programmers will have to venture into third party libraries. Modern languages like Java and Python have followed suite as well, including massive standard libraries that can be counted on regardless of the platform that code has to be executed on. 

Common Lisp has not compromised its uniform syntax and consistent expression style during its effort either. Even in the context of the Common Lisp Object System (Common Lisp's answer to object oriented programming), the same functions can be used to interact with and assign object values.

\begin{figure}[H]
\begin{lstlisting}
; asign a value to a variable
(setf var 5)

; assign a value to an object member
(setf (slot-value object `slot) "value")

; assign an array to a variable
(setf v (make-array 4))

; insert a new value into a hash table
(setf (gethash 4 table) 20)
\end{lstlisting}
\caption{Assigning in Common Lisp}
\label{fig:assign}
\end{figure}

Figure \ref{fig:assign} demonstrates the single way in which to assign values in Common Lisp and the semantics of each statement. The \texttt{setf} function takes a sequence of one or more two argument pairs, one that is assigned to (an l-value) and one that is used to assign (an r-value). Each one can be forms or expressions themselves which ultimately evaluate to a single value used for assignment. 

%Beyond this there is not much to talk about when it comes to assignments in Common Lisp (which is the beauty of it). The parenthesized prefix syntax makes precedence clear as well, as forms are simply evaluated recursively. 

%The following sections will provide some insight into the massive selection of built in types and functions in Common Lisp. 

%----------------------------------------------------------------------
% SECTION II: Assignments
%----------------------------------------------------------------------
\section{Assignments}\label{sec:assign}

The expressions shown in figure \ref{fig:assign} were a natural evolution from previous forms of Lisp. Historically, Lisp has always used the \texttt{set} function for assignment.

\begin{figure}[H]
\begin{lstlisting}
 (set `variable 50)
variable => 50
\end{lstlisting}
\caption{Original Assignment Form in Lisp}
\label{fig:original}
\end{figure}

The first argument of \texttt{set} is a variable name, the second is a value to set from, and the rest are repeating pairs of these two. Notice the back quote preceding the variable name above. This was introduced to resolve a particular ambiguity in the language. That is, there has to be a way to specify the value you intend on referencing when lists can be variables as well as programs waiting to be evaluated\cite{common_lisp_variables}. This is easiest to see in an example.

\begin{figure}[H]
\begin{lstlisting}
 (set `var1 (+ 4 5) )
var1 => 9
 (set `var2 `(+ 4 5) )
var2 => (+ 4 5)
\end{lstlisting}
\caption{Quoted and Unquoted R-Values}
\label{fig:quote}
\end{figure}
 
Both \texttt{var1} and \texttt{var2} are assigned what seems like the same list, the difference being that one is back quoted and one is not. The presence of this back quote tells the interpreter that the list should not be evaluated (hence, the distinction between variable and program). Without a back quote, the list is evaluated and the return value is assigned to the variable. With the back quote, the list is treated as a variable and assigned. The back quote appears before the variable name for the same reason. 

The first argument to \texttt{set} is usually quoted. For this reason, the special form \texttt{setq} was introduced, which behaves exactly like \texttt{set} does, except it automatically back quotes the l-values within its expression. So the above example can be rewritten as follows, without changing the semantics.

\begin{figure}[H]
\begin{lstlisting}
 (setq var1 (+ 4 5) )
var1 => 9
 (setq var2 `(+ 4 5) )
var2 => (+ 4 5)
\end{lstlisting}
\caption{\texttt{setq}}
\label{fig:quoted}
\end{figure}

While \texttt{setq} was a convenience driven change, the introduction of \texttt{setf} had a more significant purpose. The main difference between the two is that \texttt{setq} assigns exclusively to symbols, where as \texttt{setf} can take a form in place of a symbol. \texttt{setf} is actually a macro defined using the \texttt{setq} form which expands to evaluate the assignment argument before assigning it (the macro system will be discussed in a future paper). 

\begin{figure}[H]
\begin{lstlisting}
 (defvar myList `(1 2 3 4))

 (setf (car myList) 5)
myList => (5 2 3 4)
\end{lstlisting}
\caption{Forms in setf Assignments}
\label{fig:setf}
\end{figure}

The code above can be rewritten with \texttt{setq} exclusively as follows.

\begin{figure}[H]
\begin{lstlisting}
(let ((x (cdr myList)))
  (progn
    (setq x (append `(5) x ))
    (setq myList x)))

myList => (5 2 3 4)
\end{lstlisting}
\caption{Avoiding setf}
\label{fig:setq}
\end{figure}

Clearly \texttt{setf} is a very useful addition to the language. In section \ref{sec:clos} there will be examples where \texttt{setf} can be used to modify members of Common Lisp classes; another tedious task for \texttt{setq}.

When multiple pairs are specified for a \texttt{setf} expression they are all evaluated sequentially; \texttt{psetf} is provided for parallel evaluation.

\begin{figure}[H]
\begin{lstlisting}
(let ( (x 3) (y 5) )
  (setf x y y x)
  (print x)
  (print y))
x => 5
y => 5

(let ( (x 3) (y 5) )
  (psetf x y y x)
  (print x)
  (print y))
x => 5
y => 3
\end{lstlisting}
\caption{\texttt{setf} vs \texttt{psetf}}
\label{fig:psetf}
\end{figure}

\texttt{setf} first evaluates \texttt{y} and assigns it to \texttt{x}, then assigned the new value of \texttt{x} back to \texttt{y}, making them the same value. \texttt{psetf} first evaluates \texttt{x} and \texttt{y} before performing either assignment. 

\texttt{setf}'s functionality is preserved throughout Common Lisp, regardless of the type of data it is operating on. The following section will discuss some of the potential data types encountered in Common Lisp.

%----------------------------------------------------------------------
% SECTION II: Data Types
%----------------------------------------------------------------------

\section{Data Types}\label{sec:types}
Common Lisp is rich in data types despite being a dynamically typed language. This section will give an overview of the more common data types.


%----------------------------------------------------------------------
\subsection{Symbols}\label{sec:symbols}
The \textit{symbol} type is where Common Lisp (Lisp in general) starts to shine as a unique language. A \textit{symbol} is composed of three main components.

\begin{itemize}
\item \textbf{Property List}. This is a list of key-value pairs that belong to the symbol. Common Lisp has built in hash tables and lists that are easier to work with. Consequently, property lists are not used as often as they once were.
\item \textbf{Package Cell}. Refers to the \textit{package} object that owns the symbol. Packages were Common Lisps answer to name collisions in large scale applications, similar in concept to modern day Java packages. 
\item \textbf{Print Name}. This is the name associated with the symbol, analogous to a variable name, but represented as a string. This name is used to find a symbol in a particular package as well as reference a symbol directly. 
\end{itemize}

Each of these properties is free to be defined and redefined by the programmer just like any other variable. One very powerful an interesting feature of symbols in Common Lisp is the ability to bind a symbol to a function and a value simultaneously. The following code demonstrates this. A value bound variable is referred to as \textit{bound}, while a function bound variable is referred to as \textit{fbound}.

\begin{figure}[H]
\begin{lstlisting}
; create a function
(defun fun (string)
  (print string)
  string)


(setf sym (make-symbol ``sym''))                      ; create a symbol sym
(setf (symbol-function `sym) (symbol-function `fun))  ; fbind sym
(setf sym 5)                                          ; bind sym

(sym (fun 20))
==> 20
20

(sym (fun sym))
==> 5
5

(print sym)
==> 5
\end{lstlisting}
\caption{}
\label{fig:symbols}
\end{figure}

The symbol \texttt{sym} is created from a string (print name), then it is \textit{fbound} and bound. That symbol can then be used to call the \texttt{fun} function or to represent the value 5 depending on the context.

%----------------------------------------------------------------------
\subsection{Lists and Conses}\label{sec:lists}
Lists are the core data structure of Common Lisp. The easiest way to understand them is to think of them as singly linked lists composed of nodes where each node is called a cons. Like a node, a cons has a link to the next cons in the list, which is referred to as a \textit{cdr}. The first cons in a list is referred to as a \textit{car}. Common Lisp has functions named \texttt{cdr} and \texttt{car} that return conses and element data, respectively. 

\begin{figure}[H]
\begin{lstlisting}
 (setf x `(1 2 3 4))
 (print x)       ; the list
x => (1 2 3 4)

 (print (car x)) ; the first element
x => 1

 (print (cdr x)) ; the list that the first element points to
x => (2 3 4)
\end{lstlisting}
\caption{}
\label{fig:symbols}
\end{figure}

The \texttt{car} and \texttt{cdr} forms can be combined to create \texttt{cadr} which is equivalent to calling \texttt{(car (cdr `(1 2 3 4)))}. The ``a'' and the ``d'' can also be repeated up to four times as a convenient method to express a long nested \texttt{car} or \texttt{cdr} expression. For example, \texttt{(cdr (cdr (cdr `(1 2 3 4))))} can be represented as \texttt{(cdddr `(1 2 3 4))}. 

Lists in Common Lisp are always \texttt{nil} terminated unless a dot notation is used. Representing a list as \texttt{(1 2 3 . 4)} would return a list with three elements in it, the third of which would have an integer \texttt{cdr} of 4, as opposed to \texttt{nil} or another conse. 


%----------------------------------------------------------------------
\subsection{Arrays}\label{sec:arrays}

A common misconception is that Common Lisp has no array structures. While it may be true that the main data structure is linked lists, Common Lisp provides facilities to work with arrays as well. The question then becomes: when should an array be used over a list? The answer is no different in Common Lisp than any other language. Guy Steele summarizes this in his Common Lisp specification as follows\cite{common_lisp_vector}. \\

\noindent \textit{``They differ in that any component of a one-dimensional array can be accessed in constant time, whereas the average component access time for a list is linear in the length of the list; on the other hand, adding a new element to the front of a list takes constant time, whereas the same operation on an array takes time linear in the length of the array.''} \\

Arrays can be declared similar to a list and manipulated with a series of functions designed specifically for them. 

\begin{figure}[H]
\begin{lstlisting}
(setf vector #(1 2 3 4))
\end{lstlisting}
\caption{Creating a Simple Vector}
\label{fig:simple-vector}
\end{figure}

The object created in the code above has a few properties because of the way in which is was created (without the use of \texttt{make-array}). While it is an array, it is officially of the sub type \textit{vector}, which means it is one dimensional. It is also considered to be \textit{simple}, which means that it does not grow and has no \textit{fill-pointer}. A \textit{fill-pointer} is an integer associated with a vector that can be no smaller than 0, and no larger than the size of the vector, and used in vector specific functions. Programmers can use \texttt{make-array} to take advantage of available functionality.

\begin{figure}[H]
\begin{lstlisting}
 ; create an empty vector of length 4 and                                                   
 ; a fill pointer of 2, of type number
 ; and is adjustable (allowed to grow)                                                      
 (setf v (make-array 4 :fill-pointer 2 
 	:adjustable t
 	:element-type number))
v => #(NIL NIL)
 ; use the fill-pointer to add "3" to index 2                                               
 (vector-push 3 v)
v => #(NIL NIL 3)
 ; set the fill-pointer to 0, effectively                                                   
 ; making it of length 0                                                                    
 (setf (fill-pointer v) 0)
v => #()
 ; add one to vector                                                                        
 (vector-push 1 v)
v => #(1)
 ; the rest of the "inactive" list has not been                                             
 ; deleted and is still accessible by index                                                 
(print (aref v 2)) => 3
\end{lstlisting}
\caption{Creating a Vector}
\label{fig:vector}
\end{figure}

The above code demonstrates some of the functionality available for use with arrays. The concept of a \textit{fill-pointer} was mentioned earlier. This is a simple construct that acts as a pointer to where the end of an array should be. In figure \ref{fig:vector}, 3 was added to the vector using the \texttt{vector-push} function. This function takes an element and inserts it into the vector at index \texttt{fill-pointer}, which was 2. This function, along with other \texttt{vector-\*} functions, require the vector not to be simple (must have at least a \texttt{fill-pointer} defined using \texttt{make-array}). 

The vector above is also declared to be \textit{adjustable}. A vector that is \textit{adjustable} is able to change its size through functions like \texttt{adjust-array} and \texttt{vector-push-extend}. The latter function differers from \texttt{vector-push} in that it expands an \textit{adjustable} vector if there is no room\cite{cl_api}.

Making distinctions between simple and non-simple arrays has the added benefit of enabling Common Lisp implementations to optimize. Steele mentioned one specific example for possible optimizations\cite{common_lisp_vector}.

\noindent \textit{``Some implementations can handle simple arrays in an especially efficient manner; for example, simple arrays may have a more compact representation than non-simple arrays.''}

The same logic applies to specifying a type for a vector; there is a trade off between utility and efficiency. If an untyped array is not needed then it is probably a good idea to specify a type. 

It is also worth mentioning that string support is implemented through typed \textit{character} vectors, and all of the above applies to them as well. 



%----------------------------------------------------------------------
\subsection{Hash Tables}\label{sec:hash}


Hash tables in Common Lisp are superficially what one would expect; they take one object and use a hashing algorithm to map it to another object. They do, however, come in a few different flavors depending on what it is being hashed. For example, say a hash table needs only to handle integers. The following code shows how to create a basic hash table with this property.

\begin{figure}[H]
\begin{lstlisting}
 ; create a basic hash-table
 (setf table (make-hash-table))
 ; add an element to the hash-table
 (setf (gethash 4 table) 20)
(gethash 4 table) => 20
(gethash 5 table) => NIL

 ; fail to add a string as a key
 (setf (gethash "key" table) 30)
(gethash "key" table) => NIL
\end{lstlisting}
\caption{Creating a Hash Table}
\label{fig:hash-eql}
\end{figure}

As stated, the above hash table does a good job of handling integers but not strings. In fact, it can handle anything that can be compared using the \texttt{eql} function\cite{common_lisp_hash}. If strings were to be used as keys then the following code could be used. 

\begin{figure}[H]
\begin{lstlisting}
 ; create a hash-table with equal as the 
 ; test function
 (setf table (make-hash-table :test `equal))
 (setf (gethash "key1" table) 20)
 (setf (gethash 2 table) 30)
(gethash "key1" table) => 20
(gethash 1 table) => 30
\end{lstlisting}
\caption{Creating a Hash Table}
\label{fig:hash}
\end{figure}
 
This hash table is capable of hashing anything that can be tested with the \texttt{equal} function, which includes integers. There are four options in total when it comes to hash tests: \texttt{eq}, \texttt{eql}, \texttt{equal}, and \texttt{equalp}. The hash table in figure \ref{fig:hash} could have contained case insensitive keys had it used the \texttt{equalp} test instead.




%----------------------------------------------------------------------
% SECTION III: CLOS
%----------------------------------------------------------------------

%----------------------------------------------------------------------
\section{The Common Lisp Object System}\label{sec:clos}

Common Lisp had one of the earliest object oriented systems available: The Common Lisp Object System (CLOS). A simple use of CLOS is shown below.

\begin{figure}[H]
\begin{lstlisting}
(defclass counter ()
  ((count :initform 10)))
\end{lstlisting}
\caption{Creating a Simple Class}
\label{fig:clos1}
\end{figure}

Classes in Common Lisp are composed of entries called \textit{slots}. The \texttt{counter} class in figure \ref{fig:clos1} has only one slot, \texttt{count}, with an initial value of 10. The \texttt{counter} class can be expanded to include a more detailed slot definition.

\begin{figure}[H]
\begin{lstlisting}
(defclass counter ()
  ((count :initform 10
          :initarg :count
          :accessor getCount
          :type number
          :documentation "The counter class holds a number")))

(defmethod getCount ( (c counter) )
  (slot-value c `count))
\end{lstlisting}
\caption{Creating a Class}
\label{fig:clos2}
\end{figure}

This version of \texttt{counter} specifies the name of the keyword to use when initializing the value, \texttt{:count}, a method name to use when reading and writing the value of the slot, \texttt{getCount}, the type that the slot should hold, \texttt{number}, and a documentation string that describes the class.

An instance of \texttt{counter} can be created with the \texttt{make-instance} function, and interracted with like any other Common Lisp object.

\begin{figure}[H]
\begin{lstlisting}
(setf myCounter (make-instance `counter :count 44))
(print (slot-value myCounter `count)) => 44

(setf (getCount myCounter) 55)
(print (slot-value myCounter `count)) => 55
\end{lstlisting}
\caption{Creating an Instance of a Class}
\label{fig:clos3}
\end{figure}

Notice that the value of  \texttt{count} can be modified using \texttt{setf}. This is because the \texttt{getCount} method was declared as the class's \texttt{:accessor} function. Had it been declared as its \texttt{reader} function, this would not be possible.

It is also worth noting that this style of object interaction was very influential on other languages and frameworks. It bears a direct resemblance to the meta-object system in a C++ framework called Qt. An example can be seen in the appendix. 


%----------------------------------------------------------------------
% SECTION X: Conclusion
%----------------------------------------------------------------------
\section{Conclusion}\label{sec:conc}

The main goal of this paper was to examine the various types of data types and structures available in Common Lisp. In doing so, we have also showcased the uniform syntax and semantics of Common Lisp expressions in every facet of the language. Whether it be assigning integer values to variables or changing the values of class members in the CLOS system, one macro, with one expression type, can be used to do anything. 


\end{multicols}
\newpage
%----------------------------------------------------------------------
% SECTION X: APENDIX
%----------------------------------------------------------------------
\section{Apendix}\label{sec:apendix}
\subsection{Meta Object system in the Qt framework resembling the Common Lisp Object System}

Snippet taken from the Qt online API\cite{qt_property}. The similarities occur in the \texttt{Q\_PROPERTY} macro, where a name is defined for the property (essentially a variable) along with a function used to read from it and write to it. 

\begin{lstlisting}
class MyClass : public QObject
 {
     Q_OBJECT
     Q_PROPERTY(Priority priority READ priority WRITE setPriority NOTIFY priorityChanged)
     Q_ENUMS(Priority)

 public:
     MyClass(QObject *parent = 0);
     ~MyClass();

     enum Priority { High, Low, VeryHigh, VeryLow };

     void setPriority(Priority priority)
     {
         m_priority = priority;
         emit priorityChanged(priority);
     }
     Priority priority() const
     { return m_priority; }

 signals:
     void priorityChanged(Priority);

 private:
     Priority m_priority;
 };
\end{lstlisting}

%----------------------------------------------------------------------
% SECTION X: Bibliography
%----------------------------------------------------------------------

\newpage
\thispagestyle{empty}
\begin{thebibliography}{1}
\bibliographystyle{IEEEbib}
\bibliography{bibliography}
\end{thebibliography}

\end{document}









